//One way to serialize a binary tree is to use preorder traversal. When we encou
//nter a non-null node, we record the node's value. If it is a null node, we recor
//d using a sentinel value such as '#'. 
//
// For example, the above binary tree can be serialized to the string "9,3,4,#,#
//,1,#,#,2,#,6,#,#", where '#' represents a null node. 
//
// Given a string of comma-separated values preorder, return true if it is a cor
//rect preorder traversal serialization of a binary tree. 
//
// It is guaranteed that each comma-separated value in the string must be either
// an integer or a character '#' representing null pointer. 
//
// You may assume that the input format is always valid. 
//
// 
// For example, it could never contain two consecutive commas, such as "1,,3". 
// 
//
// 
// Example 1: 
// Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
//Output: true
// Example 2: 
// Input: preorder = "1,#"
//Output: false
// Example 3: 
// Input: preorder = "9,#,#,1"
//Output: false
// 
// 
// Constraints: 
//
// 
// 1 <= preorder.length <= 104 
// preoder consist of integers in the range [0, 100] and '#' separated by commas
// ','. 
// 
//
// 
// Follow up: Find an algorithm without reconstructing the tree. 
// Related Topics 栈 
// 👍 310 👎 0


package leetcode.editor.cn;

import java.util.Stack;

//Java：Verify Preorder Serialization of a Binary Tree
class P331VerifyPreorderSerializationOfABinaryTree {
    public static void main(String[] args) {
        Solution solution = new P331VerifyPreorderSerializationOfABinaryTree().new Solution();
        // TO TEST
        System.out.println(solution.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isValidSerialization(String preorder) {
            String[] arr = preorder.split(",");
            Stack<String> stack = new Stack<>();
            for (int i = 0; i < arr.length; i++) {
                String s = arr[i];
                if (s.equals("#")) {
                    while (!stack.isEmpty() && stack.peek().equals("#")) {
                        stack.pop();
                        if (!stack.isEmpty()) {
                            stack.pop();
                        } else {
                            return false;
                        }
                    }
                    stack.push("#");
                } else {
                    stack.push(s);
                }

            }
            return stack.size() == 1 && stack.peek().equals("#") ? true : false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}